package java1024;
import java.util.*;
class ListNode {
    int val;
    ListNode next;

    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class TestDemo2 {
    public int[][] solve (int[][] a, int[][] b) {
        // write code here
        int[][] arr=new int[a.length][a[0].length];
        for (int i = 0; i < a.length; i++) {
            int sum=0;
            for (int j = 0; j < a[i].length; j++) {
                for (int k = 0; k < b.length; k++) {
                    sum=sum+a[j][k]*b[k][j];
                }
            }
            arr[i][i]=sum;
        }
        return arr;
    }
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        if (head1==null) return head2;
        if (head2==null) return head1;
        Stack<ListNode> stack1=new Stack<>();
        Stack<ListNode> stack2=new Stack<>();
        while (head1!=null){
            stack1.push(head1);
            head1=head1.next;
        }
        while (head2!=null){
            stack2.push(head2);
            head2=head2.next;
        }
        int tmp=0;
        ListNode listNode=new ListNode(-1);
        ListNode n1=listNode.next;
        while (!stack1.isEmpty()||!stack2.isEmpty()){
            int val=tmp;
            if (!stack1.isEmpty()){
                val+=stack1.pop().val;
            }
            if (!stack2.isEmpty()){
                val+=stack2.pop().val;
            }
            tmp=val/10;
            ListNode node=new ListNode(val%10);
            node.next=n1;
            n1=node;
        }
        if (tmp>0){
            ListNode node=new ListNode(tmp);
            node.next=n1;
            n1=node;
        }
        return n1;
    }
    public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        if (pHead==null||k<=0){
            return null;
        }
        ListNode fast=pHead;
        ListNode n1=pHead;
        for (int i = 0; i < k-1&&fast!=null; i++) {
            fast=fast.next;
        }
        if (fast==null){
            return null;
        }
        while (fast.next!=null){
            fast=fast.next;
            n1=n1.next;
        }
        return n1;
    }
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        if (pHead1==null||pHead2==null){
            return null;
        }
        int count1=0;
        int count2=0;
        ListNode n1=pHead1;
        ListNode n2=pHead2;
        while (n1!=null){
            count1++;
            n1=n1.next;
        }
        while (n2!=null){
            count2++;
            n2=n2.next;
        }
        if (count1>count2){
            for (int i = 0; i < count1-count2; i++) {
                pHead1=pHead1.next;
            }
        }
        else if(count2>count1){
            for (int i = 0; i < count2-count1; i++) {
                pHead2=pHead2.next;
            }
        }
        while (pHead1!=null&&pHead2!=null){
            if (pHead1==pHead2){
                return pHead1;
            }
            pHead1=pHead1.next;
            pHead2=pHead2.next;
        }
        return null;
    }
    public ListNode mergeKLists(ArrayList<ListNode> lists) {
        if(lists.isEmpty()||lists.size()==0){
            return null;
        }
        PriorityQueue<ListNode> queue=new PriorityQueue<>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        for (int i = 0; i < lists.size(); i++) {
            if(lists.get(i)!=null){
                queue.offer(lists.get(i));
            }
        }
        ListNode n1=new ListNode(-1);
        ListNode n2=n1;
        while (!queue.isEmpty()){
            ListNode n3= queue.poll();
            n2.next=n3;
            n2=n2.next;
            if(n3.next!=null){
                queue.offer(n3.next);
            }
        }
        return n1.next;
    }
}

